package done.normal_901_1000;

import com.study.common.TreeNode;
import org.junit.Test;

import static com.study.util.LogUtil.info;

/**
 * 998. Maximum Binary Tree II 最大二叉树 II
 * <p>
 * 最大树定义：一个树，其中每个节点的值都大于其子树中的任何其他值。
 * 给出最大树的根节点 root。
 * 就像之前的问题那样，给定的树是从表 A（root = Construct(A)）
 * 递归地使用下述 Construct(A) 例程构造的：
 * <p>
 * 如果 A 为空，返回 null
 * 否则，令 A[i] 作为 A 的最大元素。创建一个值为 A[i] 的根节点 root
 * root 的左子树将被构建为 Construct([A[0], A[1], ..., A[i-1]])
 * root 的右子树将被构建为 Construct([A[i+1], A[i+2], ..., A[A.length - 1]])
 * 返回 root
 * 请注意，我们没有直接给定 A，只有一个根节点 root = Construct(A).
 * 假设 B 是 A 的副本，并附加值 val。保证 B 中的值是不同的。
 * 返回 Construct(B)。
 * <p>
 * 示例 1：
 * 4
 * /   \
 * 1     3
 * /
 * 2
 * <p>
 * 加一个 5 节点, 变成下面的样子
 * <p>
 * 5
 * /
 * 4
 * /   \
 * 1     3
 * /
 * 2
 * <p>
 * 输入：root = [4,1,3,null,null,2], val = 5
 * 输出：[5,4,null,1,3,null,null,2]
 * 解释：A = [1,4,2,3], B = [1,4,2,3,5]
 *
 * @author 大硕
 * 2019-05-15 22:27
 **/
@SuppressWarnings("all")
public class MaximumBinaryTreeII {

    public TreeNode insertIntoMaxTree(TreeNode root, int val) {
        if (root == null) {
            return root;
        }
        return dfs(root, val);
    }

    private TreeNode dfs(TreeNode root, int val) {
        if (root == null) {
            root = new TreeNode(val);
        } else {
            //原根节点添加到左边
            if (root.val <= val) {
                TreeNode temp = root;
                root = new TreeNode(val);
                root.left = temp;
            } else {
                root.right = dfs(root.right, val);
            }
        }
        return root;
    }

    @Test
    public void test() {
        info(insertIntoMaxTree(new TreeNode(4,
                1, new TreeNode(3,
                2, null)), 5));
    }
}





























/*
public TreeNode insertIntoMaxTree(TreeNode root, int val) {
    if(root == null){
        return root;
    }
    return iMT(root,val);
}

private TreeNode iMT(TreeNode root, int val){
    if(root == null){
        root = new TreeNode(val);
    }
    else{
        //原根节点添加到左边
        if(root.val <= val){
            TreeNode temp = root;
            root = new TreeNode(val);
            root.left = temp;
        }
        else{
            root.right = iMT(root.right, val);
        }
    }
    return root;
}
*/
